package pri.zjy.queue;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author zhangjy
 * @description 数组中的第K个最大元素
 * @date 2025/4/3 11:55
 */
public class FindKthLargest_215 {

    public static void main(String[] args) {
        FindKthLargest_215 findKthLargest215 = new FindKthLargest_215();

        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println(findKthLargest215.findKthLargest2(nums, k));

        // TODO 手动建堆
        // TODO 快排实现

    }

    /**
     * 个解：优先级队列实现小顶堆
     */
    public int findKthLargest3(int[] nums, int k) {
        // 优先级队列实现小顶堆，记录前k个大的元素，最后返回第k个大的元素

        // 1.优先级队列记录 k 个元素
        // 根据元素值从小到大排列，实现小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((e1, e2) -> e1 - e2);
        for (int i = 0; i < nums.length; i++) {
            // pq已满，若新元素 > 队首，则先出队
            if (pq.size() == k) {
                if (nums[i] > pq.peek()) pq.poll();
            }
            // pq未满，直接入队
            if (pq.size() < k) pq.offer(nums[i]);
        }

        // 2.记录到数组
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = pq.poll();
        }

        // ans存储前k个大的元素，那么原nums中第k大的就是ans[0]
        return ans[0];
    }

    /**
     * 个解：优先级队列实现小顶堆
     */
    public int findKthLargest2(int[] nums, int k) {
        // 小顶堆（只记录 前k个 大的元素）
        PriorityQueue<Integer> queue = new PriorityQueue<>((p1, p2) -> p1 - p2);
        for (int i = 0; i < nums.length; i++) {
            if (queue.size() < k) {
                // 队列未满，则直接入队
                queue.add(nums[i]);
            } else {
                // 否则，根据小顶堆规则决定是否入队
                if (nums[i] > queue.peek()) {
                    queue.poll();
                    queue.add(nums[i]);
                }
            }
        }

        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = queue.poll();
        }

        // 小顶堆按 从小到大 顺序记录 前k个 大的元素，所以第一个就是目标值
        return ans[0];
    }

    /**
     * 该方法不行;
     * 因为快排最好情况，T(n) = O(nlogn)；但是最坏情况，T(n) = O(n^2)，这不满足题目
     */
    public int findKthLargest(int[] nums, int k) {
        if (nums.length == 0) return -1;

        // 升序排列
        Arrays.sort(nums);

        return nums[nums.length - k];
    }

}
